#include "stdafx.h"
#include <iostream>
using namespace std;

struct node
{
    int son_1;
	int son_2;
	bool son_1_fixed;
	bool son_2_fixed;
};

void f_setson(node father,int sonName);
void f_print(node *or_arr,int nodename,bool end);//子节点1或2的情况
void f_print(node *arr, int nodename_1, int nodename_2); //子节点两个 且这两个都有子节点的情况


int main()
{
	int n_line,n_node;
	node *output = new node[n_node];
	for (size_t i = 0; i < n_node; i++) //初始化所有节点
	{   
		output[i].son_1 = 0; //1是根节点
		output[i].son_2 = 0;
		output[i].son_1_fixed = false;
		output[i].son_2_fixed = false;
	}


	for (size_t i = 0; i < n_line*2; i++)
	{
		int son;
		int father;
		cin >> son;
		cin >> father;
		f_setson(output[father], son);
	}//设定部分


	system("pause");
}

void f_setson(node father, int sonName) //设定子节点
{/*考虑：题目要求先左节点再右节点
        |——左节点是否marked？
		| marked：
		|          右节点是否marked？
		|          marked 退出程序
		|！marked：
		          设定右节点
		|——！marked：设定左节点
		*/
	if (father.son_1_fixed)
	{
		if (father.son_2_fixed)
		{
			return;
		}
		else
		{
			father.son_2 = sonName;
			father.son_2_fixed = true;
		}
	}
	else
	{
		father.son_1 = sonName;
		father.son_1_fixed = true;
	}
}

void f_print(node * or_arr, int nodename, bool end) //输出部分是个难啃的骨头啊！！！
{
	if (or_arr[nodename].son_1_fixed)
	{
		cout << or_arr[nodename].son_1;
	}
	if (or_arr[nodename].son_2_fixed)
	{
		cout << " " << or_arr[nodename].son_2;
	}
	if (end)
	{
		cout << endl;
	}
	if (or_arr[nodename].son_1_fixed&&or_arr[nodename].son_2_fixed)
	{
		if (or_arr[or_arr[nodename].son_1].son_1_fixed&&or_arr[or_arr[nodename].son_2].son_1_fixed)
		{
			f_print(or_arr, or_arr[nodename].son_1,false);
			cout << " ";
			f_print(or_arr, or_arr[nodename].son_2,true);
		}
	}

}

